import java.util.Arrays;

/**
 * 面试题29：顺时针打印矩阵
 */
public class Offer_29 {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[] {};
        }

        // 矩阵的上边界、下边界、左边界、右边界
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        // 结果数组
        int[] ans = new int[(bottom + 1) * (right + 1)];
        // 结果数组下标
        int x = 0;

        while (true) {
            // 从左到右
            for (int i = left; i <= right; i++) {
                ans[x++] = matrix[top][i];
            }
            if (++top > bottom) {
                break;
            }
            // 从上到下
            for (int i = top; i <= bottom; i++) {
                ans[x++] = matrix[i][right];
            }
            if (--right < left) {
                break;
            }
            // 从右到左
            for (int i = right; i >= left; i--) {
                ans[x++] = matrix[bottom][i];
            }
            if (--bottom < top) {
                break;
            }
            // 从下到上
            for (int i = bottom; i >= top; i--) {
                ans[x++] = matrix[i][left];
            }
            if (++left > right) {
                break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Offer_29 solution = new Offer_29();
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
        int[] ans = solution.spiralOrder(matrix);
        System.out.println(Arrays.toString(ans));
    }
}
